Locality-Sensitive Hashing
$$ \gdef\S{\mathrm{S}} \gdef\darc{d_{\mathrm{arc}}} \gdef\a#1#2{\mathrm{A}_{#1}\p{#2}} \gdef\sign#1{\mathrm{sign}\p{#1}} $$
Let $\S_n$ be an $n$-dimensional unit $n$-sphere
$$ \begin{align} \mathrm{S}_n = \setb{\vec x ∈ \R^n}{\norm{\vec x}_2 = 1} \end{align} $$
and let $\darc$ be the arc length distance
$$ \begin{align} \darc\p{\vec a, \vec b} = \cos^{-1}\p{\vec a ⋅ \vec b} \end{align} $$
Random projections
-
$\mathcal S$ The uniform distribution on $\S^n$.
-
$\mathcal F$ The distribution by constructing.
-
$n$ The number of dimensions.
-
$m$ The number of hyperplanes in a vector.
-
$k$ The number of vectors.
Hyperplanes are defined by a normal unit vector $\vec h ∈ \S^n$. For a given vector $\vec x$ we can determine on which side of the plane it lies by the sign of the dot product $\vec x ⋅ \vec h$.
$$ \begin{align} \mathrm{Pr}_{\vec h ∈ \mathcal S}\left[\sign{\vec h ⋅ \vec a} = \sign{\vec h ⋅ \vec b} \right] = 1 - \frac{\darc\p{\vec a, \vec b}}{π} \end{align} $$
If we pick $m$ random hyperplanes $\vec h_i ∈ \S^n$ we can map each vector $\vec x ∈ \S^n$ into a $m$-bit vector $b(\vec x)$:
$$ \begin{align} b_i\p{\vec x} = \begin{cases} 0 & \vec h_i ⋅ \vec x ≤ 0 \\ 1 & \vec h_i ⋅ \vec x > 0 \end{cases} \end{align} $$
Assuming the hyperplanes are uniformly random, the probability of two bitvectors being equal is:
$$ \begin{align} \Pr{b\p{\vec a} = b\p{\vec b}} = \p{1 - \frac{\darc\p{\vec a, \vec b}}{π} }^m \end{align} $$
The hyperplanes form a tesselation of $\S^n$ where each region has a unique bitvector and each boundary represents a single bit change. Interestingly this implies that a Hamiltonian path through regions (if one exists) creates a Gray code.
We have two distributions on $\S^n$, $\mathcal{U}_{match}$ and $\mathcal{U}_{non-match}$. Given a vector $\vec x$ we want to classify it's distribution.
Assumption. Iris embeddings of different irises are uniformly distributed on $\S^n$ so the $\darc$ of non-matching irises follows the formula.
$$ \begin{align} \Pr{b\p{\vec a} = b\p{\vec b}} = \p{1 - \frac{\darc\p{\vec a, \vec b}}{π} }^m \end{align} $$
Amplification
What is the probability of a match if $\darc < T$.
We are a looking for a family of hash functions $\mathcal H$, $h: \S^n → H$ such that
- $∀_{\vec a, \vec b ∈ \S^n}\, \darc\p{\vec a, \vec b} < T → \mathrm{Pr}_{h ∈ \mathcal H}\left[h\p{\vec a} = h\p{\vec b} \right] ≥ P_1$
- $∀_{\vec a \S^n}\, \mathrm{Pr}_{h ∈ \mathcal H}\left[h\p{\vec a} = h\p{\vec b} \right] ≥ P_1$
Irreversibility
Assume we are given $H\p{\vec a}$, what can we learn about $\vec a$?
We can at best hope to learn all of the hyper-plane signs. This is $m⋅k$ bits of information. The subset of $S^n$ that has the same signs is a convex polygon with an (assumed) expected area of $2^{-m⋅k} A_n$. We would not have any more information than this, so our posterior would at best be the uniform distribution over this region.
We can start by drawing many samples from $\mathcal S$. and find matching vectors $k$.
TODO https://www.notion.so/Draft-Outline-99ecafcd45384d58a06bc1003fe1088b
https://en.wikipedia.org/wiki/Locality-sensitive_hashing
https://www.cs.princeton.edu/courses/archive/spring04/cos598B/bib/CharikarEstim.pdf
https://arxiv.org/abs/2010.09393
https://randorithms.com/2019/09/19/Visual-LSH.html
